package com.yfz.day03;

import java.util.ArrayList;
import java.util.List;

/**
 *  42 接雨水
 */
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] premax = new int[len];
        int[] sufmax = new int[len];
        premax[0] = height[0]; // 初始化左侧最大高度数组
        for (int i = 1; i < len; i++) {
            premax[i] = Math.max(premax[i - 1], height[i]);
        }
        sufmax[len - 1] = height[len - 1]; // 初始化右侧最大高度数组
        for (int i = len - 2; i >= 0; i--) {
            sufmax[i] = Math.max(sufmax[i + 1], height[i]);
        }
        int sum = 0;
        for (int i = 1; i < len - 1; i++) {
            int max = Math.min(premax[i], sufmax[i]);
            if (max - height[i] > 0) {
                sum += (max - height[i]);
            }
        }
        return sum;
    }
}